package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;
import LeetCode.interview._141_Linked_List_Cycle.ListNode;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题
	　Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. 
	　　You may assume that the array is non-empty and the majority element always exist in the array. 

题目大意
　	
解题思路

 * @Date 2017-09-14 20：09
 */
public class _169_Majority_Element {
   
	public int majorityElement(int[] num) {
		int main = num[0];		//先假设第一个就是主元素
		int count = 1;			//计数器
		for (int i = 1; i < num.length; i ++) {
			if (num[i] == main)	count++;
			else {
				/**
				 * 有一种情况：{2, 4, 2, 1, 4, 5, 4, 4, 6, 4}, 
				 * 	此时主元素为4,当遍历到索引1时,main为4;
				 * 	但是再往后遍历,遍历到索引4时,main被改为1
				 * 		但是不用担心:因为主元素是"在数组中出现次数大于一半的元素",
				 * 			即使数组前面一段4被替换掉(数组前面一段4出现次数较小),
				 * 				4一定会在遍历数组后面一段再重新被赋值(前面一段4较少,后面一段一定出现较多)
				 */
				if (count <= 0) {
					main = num[i];		//更换主元素为当前元素
					count = 1;			//count重新赋值,重新计算
				} else {
					count--;
				}
			}
		}
        return main;
    }

    public void traverse(List<Integer> list) {
    	for (int i : list) {
    		LogUtils.print(i);
    	}
    }


	public static void main(String[] args) {
		_169_Majority_Element obj = new _169_Majority_Element();
		LogUtils.println("结果", obj.majorityElement(new int[]{4, 2, 2, 1, 4, 5, 4, 4, 6, 4}));
	}

}
